package org.example.everyday;

/**
 * https://leetcode-cn.com/problems/sort-an-array/
 *
 * 快速排序
 */
public class SortArray {

    public static void main(String[] args) {

        int[] array = new int[]{5,8,3,1};

        SortArray sortArray = new SortArray();

        //快速排序
//        sortArray.quick_sort(array,0,array.length-1);

        //归并排序
        sortArray.mergetSort(array,0,array.length-1);

        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }

    }

    public void quick_sort(int[] nums,int start,int end){
        //递归的终结条件
        if(start>=end){
            return;
        }
        int piovt = nums[start];
        int left = start+1;
        int rigth = end;


        while (left<=rigth){
            if(nums[left] < piovt){
                left ++ ;
                continue;
            }
            if(nums[rigth] >= piovt){
                rigth--;
                continue;
            }
            swap(nums,left,rigth);
        }
        swap(nums,start,rigth);
        quick_sort(nums,start,rigth-1);
        quick_sort(nums,left,end);
    }

    /**
     * 归并排序的思维
     * @param nums
     * @param start
     * @param end
     */
    public void mergetSort(int[] nums,int start,int end){
        if(start >= end){
            return;
        }
        int mid = start + (end-start)/2;
        mergetSort(nums,start,mid);
        mergetSort(nums,mid+1,end);

        //最后把两个数组中的数据进行合并 排序
        merge(nums,start,mid,end);
    }

    /**
     * 归并排序
     * @param nums
     * @param start
     * @param mid
     * @param end
     */
    private void merge(int[] nums, int start, int mid, int end) {
        //定义一个临时数组，存储排序后的数组
        int[] temp = new int[end - start +1];
        //左边数组的第一个坐标
        int i = start;
        //右边数组的第一个坐标
        int j = mid+1;
        for (int idx = 0; idx < end - start +1; idx++) {
            //左边已经比较完了
            if(i > mid){
                temp[idx] = nums[j];
                j++;
                continue;
            }
            //如果右边已经比较完了
            if(j>end){
                temp[idx] = nums[i];
                i++;
                continue;
            }
            if(nums[i] < nums[j]){
                temp[idx] = nums[i];
                i++;
            }else{
                temp[idx] = nums[j];
                j++;
            }
        }

        for (int k = 0; k < end - start + 1; k++) {
            nums[start+k] = temp[k];
        }

    }


    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]  = nums[j];
        nums[j] = temp;
    }
}
